#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

void dfs(vector<int>& A, vector<int>& B, vector<int>& C, size_t n)
{
    if (n == 1) {
        C.push_back(A.back());
        A.pop_back();
        return;
    }
    dfs(A, C, B, n - 1);
    C.push_back(A.back());
    A.pop_back();
    dfs(B, A, C, n - 1);
}

void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
    dfs(A, B, C, A.size());
}


void _Mergesort(int* a, int* tmp, int begin, int end)
{
    if (begin == end)
    {
        return;
    }
    int mid = (begin+end) / 2;
    _Mergesort(a, tmp,begin ,mid );
    _Mergesort(a, tmp, mid+1, end);
   
    int begin1 = begin, end1 = mid;
    int begin2 = mid+1, end2 = end;
    int i = begin;
    while (begin1<=end1&&begin2<=end2)
    {
        if (a[begin1] <= a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }

    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}

void Mergesort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int)*n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }
    _Mergesort(a, tmp, 0, n - 1);
    free(tmp);
    tmp = NULL;
}

void swap(int* q, int* p)
{
    int tmp = *q;
    *q = *p;
    *p = tmp;
}

void _quicksort(int* a, size_t left, size_t right)
{
    if (left >= right)
        return;
    int keyi = left;
    int begin = left,end=right;
    while (begin < end)
    {
        while (begin < end && a[end] >= a[keyi])
        {
            --end;
        }
        while (begin<end&&a[begin] <= a[keyi])
        {
            ++begin;
        }
        swap(&a[begin],&a[end]);
    }
    swap(&a[keyi], &a[begin]);
    keyi = begin;
    _quicksort(a, left,keyi -1);
    _quicksort(a, keyi+1, right);
}

void quicksort(int* a, size_t n)
{
    _quicksort(a, 0, n - 1);
}

int main()
{
    int arr[10] = { 4,3,5,2,6,7,9,1,8 };
    //Mergesort(arr, 10);
    //swap(arr[0], arr[1]);
    quicksort(arr,10);
    for (size_t i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
    
}